#include "tempdefine.h"

// https://zhuanlan.zhihu.com/p/139957327

void handleSeqList()
{
    SeqList L = createSeqList(5);
    // insertSeqList(L, 5, 2);
    insertSeqList(L, 4, 3);
    printf("find element result: value=%d \n", findValueByLoca(L, 4));
    printf("delete element by position: value=%d \n", deletSeqList(L, 4));
    printArray(L);
}

void handleLinkList()
{
    SLinkList SL = createSeqLinkList();
    insertLinkList(&SL, 2, '8');
    printSLinkList(SL);
}

void handleLinkListHasHead()
{
    SLinkList SL = createSLinkListHasHead();
    insertHasHeadLinkList(SL, 2, '8');
    printSLinkList(SL);
    printf("delete element: %c \n", deleteHasHeadLinkList(SL, 1));
    printSLinkList(SL);
    printf("find element: %c \n", findHasHeadLinkList(SL, 3));
}

// 括号对匹配以及统计
void judgeBracket(char *arr)
{
    SeqStack stack = createSeqStack(100);

    int matchflag = 1;  // 匹配标识
    int bracketnum = 0; // 括号对数

    while (*arr != '\0')
    {
        if (*arr == '(')
        {
            push(stack, *arr);
        }
        else if (*arr == ')')
        {
            if (emptySeqStack(stack))
            {
                matchflag = 0;
                break;
            }
            pop(stack);
            bracketnum++;
        }
        arr++;
    }

    if (emptySeqStack(stack) && matchflag)
    {
        printf("The match brackes is %d\n", bracketnum);
    }
    else
    {
        printf("Cancel\n");
    }
}

// 进制转换。 d为转换的位数
void convertToBinary(int N, int d){
    SeqStack stack = createSeqStack(100);
    while (N)
    {
        // int 转 char 
        push(stack, (N % d) + '0');
        N = N / d;
    }

    while (!emptySeqStack(stack))
    {
        char str = pop(stack);
        printf("%c ", str);
    }
    
    printf("\n");
}

void handleSeqStack()
{
    char *chs = "(1+(3+4)*2))";
    judgeBracket(chs);
    convertToBinary(15, 2);
    exit(0);
    SeqStack stack = createSeqStack(10);
    printf("-----------seqstack push----------\n");
    char in;
    while ((in = getchar()) != '\n')
    {
        push(stack, in);
    }

    printf("----------seqstack pop-------------\n");
    while (!emptySeqStack(stack))
    {
        printf("stack pop>> %c\n", pop(stack));
    }
}

void handleSeqQueue(){
    SeqQueue myQueue = createSeqQueue(10);
    printf("---------------start queue operate-----------\n");
    char ch;
    while ((ch = getchar()) != '\n')
    {
        enQueue(myQueue, ch);
    }
    printf("---------------dequeue-----------\n");

    while (!emptySeqQueue(myQueue))
    {
        printf("dequeue>>%c\n", deQueue(myQueue));
    }
}

void handleBinaryTree(){
    BinLinkTree BLT = createByComplete();

    printf("\n前序遍历: ");
    preOrder(BLT);
    printf("\n中序遍历: ");
    inOrder(BLT);
    printf("\n后序遍历: ");
    postOrder(BLT);
    printf("\n层次遍历输出: ");
    levelTraversal(BLT);
    printf("\n求深度: %d\n", treeMaxDepth(BLT));
    printf("查找5: %s\n", findElement(BLT, '5') ? "yes": "no");
    printf("叶子结点数: %d\n", countLeafNodes(BLT));
    printf("总结点数: %d\n", countAllNodes(BLT));
    printf("\n");
}


// 递归遍历: 给定一个数组 array = {2,3,38,5,4}.  一个数字n，求数组中是否存在一个序列使得之和等于n.
int is_sequence_sum(int array[], int length, int n) {
    if (length == 0) {
        return 0;
    }

    // 如果第一个数满足条件
    if (n == 0 || array[0] == n) {
        return 1;
    }

    // 递归调用，分别考虑包含第一个数和不包含第一个数两种情况
    return is_sequence_sum(array + 1, length - 1, n - array[0]) || is_sequence_sum(array + 1, length - 1, n);
}


int main()
{
    // handleBinaryTree();

    int array[] = {2, 3, 38, 5, 4};
    int result = is_sequence_sum(array, 5, 9);
    printf("The result is %s\n", result ? "True" : "False");

    return 0;
}